package test_new;


public class MergeSort extends BubbleSort {

	public MergeSort(int[] array, IntComparator comparator) {
		super(array, null);
	}

	@Override
	public void makeBubbleSort() {
		array = mergeSort(array);

	}

	@Override
	public int[] getArray() {
		return array;
	}

	public static int[] mergeSort(int[] arr) {  
		if (arr.length <= 1)  return arr;  

		int mid = arr.length / 2;  
		int[] left = new int[mid];  
		int[] right = new int[mid + arr.length%2];  

		int j = 0;  
		for (int i = 0; i < arr.length; i++) {  
			if (i < arr.length / 2) {  
				left[i] = arr[i];  
			} else {  
				right[j++] = arr[i];  
			}  
		}  
		return Merge(mergeSort(left), mergeSort(right));  
	}  

	public static int[] Merge(int[] left, int[] right) {  
		int a = 0, b = 0;  
		int[] merged = new int[left.length + right.length];  
		for (int i = 0; i < left.length + right.length; i++) {  
			if (b < right.length && a < left.length)  
				if (left[a] > right[b] && b < right.length)  
					merged[i] = right[b++];  
				else  
					merged[i] = left[a++];  
			else  
				if (b < right.length)  
					merged[i] = right[b++];  
				else  
					merged[i] = left[a++];  
		}  
		return merged;  
	}  


}

